package com.SuanFa.lanqiao;

//振兴中华
public class a3 {

    private static final String words = "从我做起振兴中华";
    private static int count = 0;
    private static final int[][] nums = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    private static final char[][] GRID = {
            {'从', '我', '做', '起', '振'},
            {'我', '做', '起', '振', '兴'},
            {'做', '起', '振', '兴', '中'},
            {'起', '振', '兴', '中', '华'}
    };

    public static void main(String[] args) {
        dfs(0, 0, 0);
        System.out.println(count);
    }

    private static void dfs(int x, int y, int index) {
        if (GRID[x][y] != words.charAt(index)) {
            return;
        }
        if (index == words.length()-1) {
            count++;
            return;
        }
        for (int[] num : nums) {
            int numx = x + num[0];
            int numy = y + num[1];
            if (numx >= 0 && numx < GRID.length && numy >= 0 && numy < GRID[0].length) {
                dfs(numx, numy, index + 1);
            }
        }
    }
}
